Ví dụ NP (độ phức tạp)

Ví dụ NP (độ phức tạp)

Tất cả các bài toán trong P.
Phiên bản quyết định của bài toán phân tích số: cho 2 số nguyên n và k, xác định xem có tồn tại 1<f<k sao cho f chia hết n.
Bài toán đồ thị đẳng cấu
Tất cả các bài toán NP-đầy đủ, chẳng hạn như: bài toán người bán hàng, bài toán xếp ba lô

Liên quan

NP NPO 1 NPO Energomash NProtect GameGuard NP-khó Npm (phần mềm) NPO Mashinostroyeniya NP-đầy đủ NP (độ phức tạp) NPO Almaz

Tài liệu tham khảo

WikiPedia: NP (độ phức tạp) http://eccc.uni-trier.de/eccc-reports/1998/TR98-00...